Content addressable memory (CAM) is a useful device for executing table lookup operations. Particularly, because of the parallel lookup capability, a user can execute thousands or even millions of comparisons with one lookup operation.
For computer systems, CAM is widely used as the address lookup table for cache memory (called cache TAG), or as the paging translation look-aside table (TLB). For communication applications, CAM is widely used to support address lookup operations for routers. Recently, the rapid growth of networking systems has triggered strong demands for high density and high speed CAM devices. For networking applications, ternary content addressable memory (TCAM) is used to store various items such as quality of service (QoS) information, filter information, access control lists (ACL), etc. A current TCAM for networking application has 256K of 72 bit entries supporting 125 million lookups per second (LPS).
However, due to the parallel lookup operation, TCAM devices require support logic, e.g., priority encoders, on their match outputs for determining the TCAM-line address of the stored data that best matches the comparison data. In order to maximize computational speed, this support priority logic is also configured for parallel operation. One prior solution utilizes an M:1 priority encoder for an M-entry TCAM, as well as M match output flops. As the quantity of entries in a TCAM increases, complexity of the support priority encoder increases at a faster rate than the number of entries, i.e., approximately N×log N. Increased support priority encoder circuit complexity, increases design and manufacturing costs. In addition, significant circuit real estate is consumed by the support prioritizing logic, with physical size quickly becoming a limiting factor in continued expansion of current TCAM systems to support desired application performance.